The High Level Data Link Control protocol was developed by the International Standards Organization (ISO). The HDLC protocol is a data link control protocol used in various networks such as ISDN (Integrated Services Digital Network). The HDLC protocol uses synchronous transmission. All transmissions are in frames. A single frame format suffices for all types of data and control exchanges.
FIG. 1 illustrates a conventional HDLC frame. The frame has the following fields:
Flag (F)--8 bits PA1 Address (A)--One or more octets (i.e., bytes) PA1 Control (C)--8 or 16 bits PA1 Data--Variable PA1 Frame Check Sequence (FCS)--16 or 32 bits PA1 Flag (F)--8 bits PA1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1
The flag, address and control fields that precede the data field are known as a header. The FCS and flag fields following the data field are referred to as a trailer.
The flag fields delimit the frame at both ends with the unique pattern 01111110. A single flag may be used as the closing flag for one frame and the opening flag for the next. All active stations attached to a link are continuously hunting for the flag sequence to synchronize on the start of a frame. While receiving a frame, a station continues to hunt for that sequence to determine the end of the frame, as the frames are not of uniform length. However, because the HDLC frame allows arbitrary bit patterns, there is no assurance that the pattern 01111110 will not appear somewhere inside the frame, thus destroying frame-level synchronization. To avoid this problem, a procedure known as bit stuffing is used. The transmitter will always insert an extra 0 bit after each occurrence of five 1's in the frame (with the exception of the flag fields). After detecting a starting flag, the receiver monitors the bit stream. When a pattern of five 1's appears, the sixth bit is examined. If this bit is 0, it is deleted. If the sixth bit is a 1 and the seventh bit is a 0, the combination is accepted as a flag. If the sixth and seventh bits are both 1, the sending station is signaling an abort condition.
The frame check sequence is applied to the remaining bits of the frame, exclusive of flags. The normal FCS is the 16-bit CRC-CCITT standard. An optional 32-bit FCS, using CRC-32, may be employed if the frame length or line reliability dictates this choice. For purposes of illustration, only the 16-bit FCS is considered herein.
The purpose of each frame check sequence (FCS) is to allow the detection by the receiver of any errors that may have occurred during the transmission of a frame. The FCS consists of 16 bits of parity checking information that is computed at the sending side, prior to bit stuffing, from the bits contained in the address, control, and data fields, if present.
The computational procedure is derived from the well-known theory of cyclic codes. It proceeds as follows: Let the k binary bits contained in the address, control, and data fields of the frame by denoted by EQU a.sub.k-1, a.sub.k-2, . . . , a.sub.1, a.sub.0
and represented algebraically by the binary polynomial EQU G(x)=a.sub.k-1 x.sup.k-1 +a.sub.k-2 x.sup.-2 + . . . +a.sub.1 x+a.sub.0
where a.sub.k-1 is the first bit following the opening flag. Also define an auxiliary polynomial EQU L(x)=x.sup.15 +x.sup.14 + . . . +x+1
and the generator polynomial EQU P(x)=x.sup.16 +x.sup.12 +x.sup.5 +1
The polynomial P(x) has been standardized by the CCITT in Recommendation V.41 for use on general user-to-network interfaces.
Compute the remainder polynomial of the modulo-2 division of the polynomial EQU x.sup.16 g(x)+x.sup.k L(x)
by P(x) and denote this remainder by EQU R(x)=r.sub.15 x.sup.15 +r.sub.14 x.sup.14 + . . . +r.sub.1 x+r.sub.0
The frame check sequence is the ones complement of the coefficients of R(x) and is represented by the polynomial EQU FCS=R(x)+L(x)
The complete frame of n=k+16 bits exclusive of the beginning and ending flags then takes the form EQU M(x)=x.sup.16 G(x)+(R(X)+L(X)
The division by the generator polynomial is performed on the data sequence that has been modified in two ways. First the multiplication of G(x) by the factor x.sup.16 is equivalent to appending 16 zeroes to the sequence and creates the space for the FCS in the frame. Second, the addition of x.sup.k L(x) to x.sup.16 G(x) corresponds to the inversion of the first 16 bits of the data sequence and provides protection against the obliteration of the opening flag.
During transmission, the message M(x) may incur errors through the deletion or addition of bits or a change in their logical value. The latter type of error can be represented by the addition of the polynomial EQU E(x)=e.sub.n-1 x.sup.n-1 +e.sub.n-2 x.sup.n-2 + . . . +e.sub.1 x+e.sub.0
to the message, so that the received message is given by EQU M.sub.r (x)=M(x)+E(x)
The receiver calculates the remainder R.sub.r (x) obtained by dividing the polynomial EQU x.sup.16 M.sub.r (x)+x.sup.n L(x)=x.sup.16 [x.sup.16 G(x)+x.sup.k L(x)+R(x)]+x.sup.16 E(x)+x.sup.16 L(x)
by the generator polynomial P(x).
Given the relationship between G(x),R(x), and L(x) imposed at the sending end, the term in square brackets is evenly divisible by P(x). The desired remainder is therefore equal to the remainder that would be obtained from the division of EQU x.sup.16 E(x)+x.sup.16 L(x)
by P(x). This shows that R.sub.r (x) does not depend on the particular data sequence but is a function of the error pattern alone.
Now suppose that the message is received without errors of any kind. Then E(x)=0, and the preceding division results in the remainder EQU R.sub.r (x)=x.sup.12 +x.sup.11 +x.sup.10 +x.sup.8 +x.sup.3 +x.sup.2 +x.sup.1 +1
Any other value of R.sub.r (x) therefore indicates the presence of errors in the received message.
A circuit 10 for a shift register implementation of the FCS calculation at the transmitter and receiver is shown in FIG. 2. The circuit 10 comprises a shift register 13 formed from the storage elements 12 and gates 9.
The addition of x.sup.k L(x) to x.sup.16 G(x) is accomplished by presetting the storage elements 12 of shift register 13 to binary 1. The register 13 calculates R(x) by enabling gates G2 and G3 and disabling via invertor 16 gate G1 using the input A. The k coefficients of G(x) arrive at the input 14 and are cycled through the register 13 via the feedback path through the gate 15 and the gate G3. At the same time the arriving data at the input 14 are shifted into the outgoing channel 25 via the gate G2 and gate 22. After k shifts, the register 13 contains the sixteen coefficients of R(x), which are then shifted into the channel 25 by enabling gate G1 and disabling gates G2 and gate G3. The inversion of the coefficients takes place in the inverter 27.
The register at the receiver, which is almost identical to the one at the transmitter, is again preset to binary 1. The entire received message M.sub.r (x) is then shifted through the register by enabling gates G2 and G3 and disabling gate G1. If the message contained no errors, the content of the register after n shifts will be the pattern
Any other error pattern would, of course, indicate the presence of one or more errors in M.sub.r (x).
The address field and control field are not of particular relevance to the present invention and are not discussed in detail herein.
Some devices connect two lines of different rates. For example, a concentrator may be collect data from many low rate terminals and place this data on a high speed transmission link connecting a host. An adapter may transform a HDLC-based protocol to another HDLC-based protocol.
FIG. 3 illustrates a system 50 in which two transmission lines with different transmission rates are connected. An external device (not shown) transmits data to device D1 on line L0. The external device may be a conventional slow rate interface such as an RS-232. Device D1 is a transceiver which receives data on the line L0 and generates HDLC-like frames which are transmitted at a low rate on the line L1, which is a low bit rate line. Device D2 is an adapter or rate converter for adapting the HDLC-like frames on line L1 to appropriate HDLC-like frames which will be transmitted at a higher rate on the high bit rate line L2.
When there are data transmitted from high bit-rate line L2 to low bit-rate line L1, the adapter can transmit each data frame as soon as it is received. The data arrives much faster than it leaves. The transmitter of the adapter will not encounter underflow. The adapter D2 may have a problem of overflow which can be solved by enlarging the size of the receiving buffer. In the reverse procedure, if the data frames are transmitted from the low-rate line L1 to the high-rate line L2, the transmitter of the adapter will have the possibility of data underflow.
Store-and-forward is the simplest method to solve this rate adaption problem. In accordance with the store-and-forward technique, the adapter or concentrator starts transmitting a data frame on the high bit rate line L2 after it receives the complete data frame from the low bit rate line L1. It first stores the whole frame in a receiving buffer. Then, the data frame is transmitted out over the high bit rate line. Under such scheme, there will be no possibility of underflow. However, the store-and-forward method has a shortcoming of having a long delay before a frame is transmitted via the high bit rate line.
A further problem with the store-and-forward technique is that the adapter D2 requires an FCS circuit, which as shown in FIG. 2 comprises a shift register and associated logic. The adapter D2 also requires bit stuffing circuitry. These circuits add to the complexity and cost of the adapter.
The problem of rate adaption may be important in certain kinds of ISDN networks. ISDN is a general purpose digital network capable of supporting access to a wide range of interconnected services such as voice, data facsimile and video. ISDN achieves the support of a large variety of services by providing a standard digital user-network interface. A standard network-user interface 60 is illustrated in FIG. 4. A public network circuit 62 (e.g., a central office switch or PABX) is connected by a trunk line 63 to the fractional network termination unit (F-NT) 65. Illustratively, the trunk line 63 has a rate of 64 kbps. A plurality of terminal equipment 68 (TE's and F-TE's) are connected via S/T buses 67a, 67b to the network termination unit 65. Some of the terminal equipment is fractional (F-TE) and transmits at a rate of 64/N kbps where N is an integer greater than 2. The remainder of the terminal equipment (TE) is standard and transmits at 64 kbps. The physical frames transmitted on the S-bus from the terminal equipment to the network termination unit 65 comprise two B channels and one D channel (see, e.g., U.S. Pat. No. 4,920,723). Illustratively, the terminal equipment generates HDLC frames which are transmitted in a B or sub-B channel of the physical frames. Rate adaptation is necessary at the network termination unit 65 of FIG. 4 to convert between the 64/N kbps bit stream transmitted on bus 67b and the 64 kpbs bit stream on the line 63.
In view of the foregoing it is an object of the present invention to provide a rate adapter and rate adaptation technique which receives frames such as HDLC frames on a low bit rate line and retransmits the frames on a high bit rate line with a minimum of delay. More specifically, it is an object of the present invention to provide a rate adapter and rate adaptation technique which overcomes the shortcomings of the store-and-forward technique described above. It is a further object of the invention to provide an adapter and adaptation technique which requires neither an FCS circuit nor a bit stuffing circuit. It is also an object of the present invention to provide an adaptation technique for use at a fractional NT in an ISDN network.